package math_01_quick_sort;

import com.alibaba.fastjson.JSONObject;

/**
 * ***********************************************************
 *
 * @类名 : math_01_quick_sort.类名
 * @DESCRIPTION : 这家伙太懒啥都没写
 * 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
 *
 * @AUTHOR :  一个风情万种的男子
 * @DATE : 2016/4/14
 * ***********************************************************
 */
public class QuickSort {
    int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};

    public void quickSort() {
        quick(a);

    }

    private void quick(int[] a) {
        if (a.length > 0) {
            _quick_sort(a, 0, a.length - 1);
        }
    }

    /**
     * 分治算法递归排序
     * @param list
     * @param low
     * @param high
     */
    private void _quick_sort(int[] list, int low, int high) {
        if (low < high) {
            int middle = getMiddle(list, low, high);//将list数组一分为二
            _quick_sort(list, low, middle - 1);//对低位数组进行递归排序
            _quick_sort(list, middle + 1, high);//对高位数组进行递归排序
        }

    }

    /**
     * 获取中轴位置
     * @param list
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] list, int low, int high) {
        int temp = list[low];//将数组的第一个做为中轴
        while (low < high) {
            while (low < high && list[high] >= temp) {
                //高位索引一直减到比中轴小的高位数停止
                high--;
            }
            list[low] = list[high];//比中轴小的高位数移到低端轴
            while (low < high && list[low] <= temp) {//到这里的temp即将与高位的数据交换了，这里的temp可以看做是高位数
                low++;
            }
            list[high] = list[low];   //比中轴大的记录移到高端
        }
        list[low] = temp; //中轴记录到尾
        return low;//返回中轴的位置
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        System.out.println("排序前的数组:" + JSONObject.toJSONString(quickSort.a));
        quickSort.quick(quickSort.a);
        System.out.println("排序后的数组:" + JSONObject.toJSONString(quickSort.a));

    }
}
